The present invention relates to an enhanced contention based medium access control method and apparatus in a communication system. More particularly, the invention relates to a protocol for monitoring communication traffic on a CATV system.
Over the past few years, the availability of CATV services to individual homes has increased dramatically. CATV systems have become increasingly popular and the diversity of available services has grown. Those services now include pay per view, on-line banking, home shopping and most importantly, internet access. CATV services are no longer limited to transmitting video programs from a headend to the settop terminals. Settop terminals may download data from the headend and upload program selections and other data to the headend. Accordingly, the volume of upstream communications from settop terminals to the headend has increased since the interactive features of CATV services require realtime feedback from the settop terminals.
A typical CATV network consists of a cable plant with the headend connected to individual settop terminals through a shared medium, such as a coaxial cable or a fiber optical cable. In a typical bi-directional CATV network, the upstream channels carry information which is transmitted from the plurality of settop terminals to the headend; and downstream channels carry information which is transmitted from the headend to the settop terminals. Since the settop terminals typically share one or more upstream channels, medium access control (MAC) is needed to manage the accessibility of the upstream channels for all settop terminals sharing the channel.
It is preferable to respond to a user's demands and allocate capacity accordingly in an asynchronous or dynamic fashion. Various MAC mechanisms have been developed to address this need. ALOHA MAC was one of the first MAC techniques developed for packet radio networks. In a simple ALOHA MAC network, a sending settop terminal first sends its data frame to the MAC controller. The settop terminal then listens for a period of time equal to the maximum possible round-trip propagation delay on the network, (twice the time it takes to send a frame between the two longest physically located users), plus a small fixed time increment. If the sending settop terminal receives an acknowledgment (ACK) response from the MAC controller within that period, the transmission was successful. Otherwise, the sending settop terminal retransmits the frame. If the sending settop terminal fails to receive an ACK after repeated transmissions, it gives up.
During transmission, a frame may be corrupted due to noise on the channel or a collision, which occurs when more than one settop terminal transmits a frame at the same time and the frames on the shared channel collide. A MAC controller may determine the correctness of an incoming frame by examining a checksum. If the checksum is correct, the receiving MAC controller immediately sends out an ACK.
One problem of a network implemented with the simplest ALOHA MAC mechanism is that the system will quickly collapse when there is a rapid increase in the number of frame collisions with increased load. Therefore, the maximum utilization of the ALOHA channel approaches only about 20% under optimum network conditions of traffic load; and in practical usage it is far lower. Slotted ALOHA MAC was developed to combat this inefficiency. Slotted ALOHA MAC divides the contended network medium into uniform time slots whose size equals the frame transmission time. Each settop terminal can only transmit its message at the beginning of a time slot. The slotted ALOHA MAC increases the overall utilization of the channel, approaching 40% under perfect circumstances of network traffic. Nevertheless, a central clock or other timing technique is required to synchronize all users in such a slotted ALOHA MAC network. Such a mechanism is usually costly and complex.
Another asynchronous access control approach is frequency-division multiple access (FDMA) where different frequencies are allocated to each settop terminal. This requires a large reservation of channel bandwidth and is inefficient for terminals that are not transmitting most of the time.
Both asynchronous access control approaches provide moderate performance for constant bandwidth and latency traffic, but do not make efficient use of bandwidth and require more expensive headend control equipment. Other asynchronous approaches include round robin, reservation and collision sense (CD/CSM).
For round robin systems, such as token ring, each user settop terminal may either decline to transmit or transmit for predetermined period of time when the user is in receipt of a token that is passed around the network. The user may not transmit when the user does have the token. This technique can be very efficient if there are not many settops on the network and they have very small amounts of data to transmit. However, user settop terminals which have no data to transmit add considerable overhead to such a system.
Reservation techniques, which are best suited for stream traffic, divide the medium into time slots. A user settop terminal wishing to transmit data reserves future slots for use via a centralized controller. This mechanism requires more complex headend equipment and fails to adequately address the need of terminals to transmit bursty data of substantial length.
More complicated and complex control mechanisms such as carrier sense multiple access (CSMA) or collision detection (CD) is widely used in many networks. These systems usually require more expensive terminal hardware and suffer some of the same network breakdown problems as ALOHA, albeit at higher network utilization.
CATV networks have unique characteristics and requirements. CATV networks are bidirectional communication networks utilizing different channels to transmit upstream and downstream data. The network may have hundreds of thousands or even millions of concurrent users receiving downstream broadcast messages simultaneously, while a majority of the users do not actively utilize an upstream channel. The huge number of users and the fact that most of the time a majority of users have no need to access upstream channels make it less efficient to implement a CATV network with either a synchronous or a round robin type MAC, which inefficiently divides access time to the upstream channels among all users equally. A complicated and costly CSMA/CD type MAC or any type of MAC that requires a central clock to synchronize all users is not justified in cost or efficiency.